﻿#region File Header
/***********************************************************************
 * Copyright © 2012 Beals Software
 * All Rights Reserved
************************************************************************
Author: Donald Beals
Date: Month Day, Year
Description: TODO: Write a description of this file here.
****************************** Change Log ******************************
MM.DD.YY - Created initial file. (dbeals)
***********************************************************************/
#endregion

#region Using Statements
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;
#endregion

namespace PolygonBasedPathfinding
{
	/// <summary>
	/// 
	/// </summary>
	public static class Helper
	{
		public static bool IsPointInsidePolygon(Point[] polygonPoints, int testX, int testY)
		{
			var counter = 0;
			var point1 = polygonPoints[0];
			for(var index = 1; index <= polygonPoints.Length; ++index)
			{
				var point2 = polygonPoints[index % polygonPoints.Length];
				if(testY > Math.Min(point1.Y, point2.Y) &&
					testY <= Math.Max(point1.Y, point2.Y) &&
					testX <= Math.Max(point1.X, point2.X) &&
					point1.Y != point2.Y)
				{
					var xinters = (testY - point1.Y) * (point2.X - point1.X) / (point2.Y - point1.Y) + point1.X;
					if(point1.X == point2.X || testX <= xinters)
						++counter;
				}
				point1 = point2;
			}

			return counter % 2 != 0;
		}

		public static bool IsPointInsidePolygon(Point[] polygonPoints, Point testPoint)
		{
			return IsPointInsidePolygon(polygonPoints, testPoint.X, testPoint.Y);
		}

		public static bool IsRectangleInsidePolygon(Point[] polygonPoints, Rectangle node)
		{
			if((IsPointInsidePolygon(polygonPoints, node.Left, node.Top) && IsPointInsidePolygon(polygonPoints, node.Right, node.Bottom)) ||
				(IsPointInsidePolygon(polygonPoints, node.Right, node.Top) && IsPointInsidePolygon(polygonPoints, node.Left, node.Bottom)))
				return true;
			return false;
		}

		public static Point[] FindMinMax(Point[] polygonPoints)
		{
			var minX = int.MaxValue;
			var minY = int.MaxValue;
			var maxX = int.MinValue;
			var maxY = int.MinValue;

			foreach(var point in polygonPoints)
			{
				if(point.X < minX)
					minX = point.X;
				if(point.Y < minY)
					minY = point.Y;

				if(point.X > maxX)
					maxX = point.X;
				if(point.Y > maxY)
					maxY = point.Y;
			}

			return new Point[]
			{
				new Point(minX, minY),
				new Point(maxX, maxY),
			};
		}

		public static Rectangle FindBounds(Point[] polygonPoints)
		{
			var minMax = FindMinMax(polygonPoints);
			return new Rectangle(minMax[0].X, minMax[0].Y, minMax[1].X - minMax[0].X, minMax[1].Y - minMax[0].Y);
		}

		public static Tuple<Rectangle, bool>[] CreateGrid(Point[] polygonPoints, int nodeWidth, int nodeHeight, out int gridWidth, out int gridHeight)
		{
			var bounds = FindBounds(polygonPoints);
			gridWidth = (int)Math.Ceiling((double)bounds.Width / nodeWidth);
			gridHeight = (int)Math.Ceiling((double)bounds.Height / nodeHeight);
			var output = new Tuple<Rectangle, bool>[gridWidth * gridHeight];

			for(var row = 0; row < gridHeight; ++row)
			{
				for(var column = 0; column < gridWidth; ++column)
				{
					var nodeBounds = new Rectangle(bounds.X + (column * nodeWidth), bounds.Y + (row * nodeHeight), nodeWidth, nodeHeight);
					output[(row * gridWidth) + column] = new Tuple<Rectangle, bool>(nodeBounds, Helper.IsRectangleInsidePolygon(polygonPoints, nodeBounds));
				}
			}

			return output;
		}
	}
}
